百度百科对于组合数的定义是：从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。 由于经常遇到一些组合数问题，所以整理一些常见的快速求组合数的方法，附上Python的实现代码。

( n m ) = n ! m ! ∗ ( n − m ) ! \binom {n}{m}=\frac {n!}{m!*(n-m)!} (mn​)=m!∗(n−m)!n!​ 可以直接调用math.factorial求得阶乘，然后算出组合数，如下：

输入：

输出：

( n m ) = ( n − 1 m − 1 ) + ( n − 1 m ) \binom {n}{m}=\binom {n-1}{m-1}+\binom {n-1}{m} (mn​)=(m−1n−1​)+(mn−1​) 递归出口就在于当n=m或者m=1的时候。

输入：

输出：

前面的两种方法，在n,m数字很大的时候，运行时间会很长。在介绍第三个方法之前，先来介绍几个概念，不当之处，欢迎指点。

百度百科：同余定理数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。

取模运算的等价变形适合加法、减法、乘法 ( a + b ) % p = ( a % p + b % p ) % p (a + b) \% p = (a \% p + b \% p) \% p (a+b)%p=(a%p+b%p)%p ( a − b ) % p = ( a % p − b % p ) % p (a - b)\% p = (a\% p - b\% p) \% p (a−b)%p=(a%p−b%p)%p ( a ∗ b ) % p = ( a % p ∗ b % p ) % p ( a * b) \% p = (a \% p * b \% p) \% p (a∗b)%p=(a%p∗b%p)%p

但是，取模运算的等价变形不符合除法 a / b % p ≠ ( a % p / b % p ) % p a/b \% p ≠ (a\%p / b\%p) \% p a/b%p​=(a%p/b%p)%p

比如： （ 100 % 20 ） % 11 = 5 % 11 = 5 （100 \% 20）\% 11 = 5 \% 11 = 5 （100%20）%11=5%11=5 （ 100 % 11 / 20 % 11 ) % 11 = ( 1 / 9 ) % 11 = 0 % 11 = 0 （100\%11 / 20\%11) \% 11 = (1 / 9) \% 11 = 0 \% 11 = 0 （100%11/20%11)%11=(1/9)%11=0%11=0

逆元：对于a和p，若a和p互素且 ( a ∗ b ) % p ≡ 1 (a * b) \% p ≡ 1 (a∗b)%p≡1 则称b为a%p的逆元。

假设c为b%p的逆元，即 b ∗ c % p = 1 b*c\%p=1 b∗c%p=1

( a / b ) % p (a / b) \% p (a/b)%p = ( a / b ) ∗ 1 % p = (a / b) * 1 \% p =(a/b)∗1%p = ( a / b ) ∗ ( b ∗ c % p ) % p =(a/b)*(b*c\%p)\%p =(a/b)∗(b∗c%p)%p = a ∗ c % p =a*c\%p =a∗c%p = ( a % p ) ∗ ( c % p ) % p =(a\%p)*(c\%p)\%p =(a%p)∗(c%p)%p

这样就把求 ( a / b ) % p (a / b) \% p (a/b)%p转化成一个 ( a % p ) ∗ ( c % p ) % p (a\%p)*(c\%p)\%p (a%p)∗(c%p)%p乘法问题。

百度百科：费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有 a ( p − 1 ) % p ≡ 1 a ^ {(p-1)} \% p ≡ 1 a(p−1)%p≡1。

a （ p − 1 ） = a （ p − 2 ） ∗ a a^{（p-1）}=a^{（p-2）} * a a（p−1）=a（p−2）∗a 所以有 a （ p − 2 ） ∗ a % p ≡ 1 a^{（p-2）} * a\%p≡1 a（p−2）∗a%p≡1 所以 a （ p − 2 ） % p a^{（p-2）}\%p a（p−2）%p是 a a a的逆元。

由于m,n很大，现在要求的是 ( n m ) % p \binom{n}{m}\%p (mn​)%p，假设 p p p取100000007，由于取模运算的等价变形不适用于除法，即： ( n m ) % p ≠ n ! % p m ! % p ∗ ( n − m ) ! % p % p \binom{n}{m}\%p≠ \frac{n!\%p}{m!\%p*(n-m)!\%p}\%p (mn​)%p​=m!%p∗(n−m)!%pn!%p​%p 根据上面求得：

( a / b ) % p = ( a % p ) ∗ ( c % p ) % p (a / b) \% p=(a\%p)*(c\%p)\%p (a/b)%p=(a%p)∗(c%p)%p c 是 b % p 的 逆 元 。 c是b\%p的逆元。 c是b%p的逆元。 就相当于我们要求出 m ! 和 ( n − m ) ! {m!和(n-m)!} m!和(n−m)!的逆元，根据 a （ p − 2 ） % p a^{（p-2）}\%p a（p−2）%p是 a a a的逆元，得到 m ! 的 逆 元 是 m ! ( p − 2 ) m!的逆元是m!^{(p-2)} m!的逆元是m!(p−2) ( n − m ) ! 的 逆 元 是 ( n − m ) ! ( p − 2 ) (n-m)!的逆元是(n-m)!^{(p-2)} (n−m)!的逆元是(n−m)!(p−2) 所以 ( n m ) % p = [ n ! % p ∗ ( m ! ( p − 2 ) % p ) ∗ ( ( n − m ) ! ( p − 2 ) % p ) ] % p \binom{n}{m}\%p=[n!\%p*(m!^{(p-2)}\%p)*((n-m)!^{(p-2)}\%p)]\%p (mn​)%p=[n!%p∗(m!(p−2)%p)∗((n−m)!(p−2)%p)]%p 下面用代码来实现：

中间的power函数是用快速幂做的，直接用Python的运算符“**”的话会非常大，会超时。 小白欢迎大佬指点~